package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">删除二叉搜索树中的节点(Delete Node in a BST)</a>
 * <p>给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。</p>
 * <p>一般来说，删除节点可分为两个步骤：
 * <ol>
 *     <li>首先找到需要删除的节点；</li>
 *     <li>如果找到了，删除它。</li>
 * </ol>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [5,3,6,2,4,null,7], key = 3
 *                      5
 *                    /   \
 *                   3     6
 *                 /  \     \
 *                2    4      7
 *      输出：[5,4,6,2,null,null,7]
 *                      5                   5
 *                    /  \                /  \
 *                   4    6              2    6
 *                  /      \              \    \
 *                 2        7              4    7
 *      解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 *          一个正确的答案是 [5,4,6,2,null,null,7],
 *          另一个正确答案是 [5,2,6,null,4,null,7]。
 *
 *  示例 2:
 *      输入: root = [5,3,6,2,4,null,7], key = 0
 *      输出: [5,3,6,2,4,null,7]
 *      解释: 二叉树不包含值为 0 的节点
 *
 * 示例 3:
 *      输入: root = [], key = 0
 *      输出: []
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>节点数的范围 [0, 10^4].</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 *     <li>节点值唯一</li>
 *     <li>root 是合法的二叉搜索树</li>
 *     <li>-10^5 <= key <= 10^5</li>
 * </ul>
 * </p>
 * <b>进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。</b>
 *
 * @author c2b
 * @since 2025/2/11 14:34
 */
public class LC0450DeleteNodeInBST_M {
    static class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            //return bfs(root, key);
            return dfs(root, key);
        }

        private TreeNode bfs(TreeNode root, int key) {
            TreeNode currNode = root;
            TreeNode currNodeParent = null;
            // 循环结束条件：currNode == null(目标节点不存在) 或 currNode.val == key，找到目标节点
            while (currNode != null && currNode.val != key) {
                currNodeParent = currNode;
                if (key < currNode.val) {       // 目标节点可能在左子树中
                    currNode = currNode.left;
                } else {                        // 目标节点可能在右子树中
                    currNode = currNode.right;
                }
            }
            // 目标节点不存在
            if (currNode == null) {
                return root;
            }
            // 目标节点存在
            TreeNode targetNode;
            if (currNode.left == null && currNode.right == null) {  // 目标节点是叶子节点，删除后该位置将变为null
                targetNode = null;
            } else if (currNode.left == null) {     // 目标节点仅有右子树，使其右子树代替其位置
                targetNode = currNode.right;
            } else if (currNode.right == null) {    // 目标节点仅有左子树，使其左子树代替其位置
                targetNode = currNode.left;
            } else {    // 目标节点既有左子树也有右子树，使其左子树成为右子树最左子节点，再使其右子树替代其位置
                TreeNode tempNode = currNode.right;
                while (tempNode.left != null) {
                    tempNode = tempNode.left;
                }
                tempNode.left = currNode.left;
                targetNode = currNode.right;
            }
            // 如果删除的是根节点，返回targetNode
            if (currNodeParent == null) {
                return targetNode;
            } else if (currNodeParent.left == currNode) {   // currNode 是其父节点的左子节点
                currNodeParent.left = targetNode;
            } else if (currNodeParent.right == currNode) {  // currNode 是其父节点的右子节点
                currNodeParent.right = targetNode;
            }
            // 如果删除的是树中的节点，返回root节点
            return root;
        }

        private TreeNode dfs(TreeNode currNode, int key) {
            if (currNode == null) {
                return null;
            }
            if (key > currNode.val) {
                currNode.right = dfs(currNode.right, key);
                return currNode;
            }
            if (key < currNode.val) {
                currNode.left = dfs(currNode.left, key);
                return currNode;
            }
            if (currNode.left == null && currNode.right == null) {
                return null;
            }
            if (currNode.left == null) {
                return currNode.right;
            }
            if (currNode.right == null) {
                return currNode.left;
            }
            // 目标节点既有左子树也有右子树，使其左子树成为右子树最左子节点，再使其右子树替代其位置
            TreeNode tempNode = currNode.right;
            while (tempNode.left != null) {
                tempNode = tempNode.left;
            }
            tempNode.left = currNode.left;
            return currNode.right;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root1 = new TreeNode(0);
        Printer.printTreeNode(solution.deleteNode(root1, 0));

        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(3);
        root2.right = new TreeNode(6);
        root2.left.left = new TreeNode(2);
        root2.left.right = new TreeNode(4);
        root2.right.right = new TreeNode(7);
        Printer.printTreeNode(solution.deleteNode(root2, 3));

        TreeNode root3 = new TreeNode(5);
        root3.left = new TreeNode(3);
        root3.right = new TreeNode(6);
        root3.left.left = new TreeNode(2);
        root3.left.right = new TreeNode(4);
        root3.right.right = new TreeNode(7);
        Printer.printTreeNode(solution.deleteNode(root3, 0));

        TreeNode root4 = new TreeNode(5);
        root4.left = new TreeNode(3);
        root4.right = new TreeNode(6);
        root4.left.left = new TreeNode(2);
        root4.left.right = new TreeNode(4);
        root4.right.right = new TreeNode(7);
        Printer.printTreeNode(solution.deleteNode(root4, 7));

        TreeNode root5 = new TreeNode(5);
        root5.left = new TreeNode(3);
        root5.right = new TreeNode(6);
        root5.left.left = new TreeNode(2);
        root5.left.right = new TreeNode(4);
        root5.right.right = new TreeNode(7);
        Printer.printTreeNode(solution.deleteNode(root5, 5));
    }
}
